A new problem in data transmission is the transmission of data that requires a high band width, is bursty, and has temporal constraints. Traditionally, data transmission has been done on the public switched networks provided by the telephone companies or on packet networks. The public switched networks are designed for interactive voice applications and so provide relatively low-bandwidth circuits that satisfy stringent temporal constraints. The packet networks are designed for the transfer of data between computer systems. The only constraint is that the data eventually arrive at its destination. The amount of bandwidth available for a transfer depends on the degree of congestion in the network. The packet networks thus typically make no guarantees about when or even in what order the data in a burst of data will arrive at its destination.
It may thus be appreciated that neither the telephone network nor the packet network is well-adapted to handle high-bandwidth, bursty data with time constraints. An example of such data is digital television which has been compressed according to the Motion Picture Experts Group ("MPEG") MPEG-2 standard, otherwise set forth in ISO/IEC 13818-1 and 13818-2.
Referring now to FIG. 1 there is illustrated therein those details of the MPEG-2 standard that are required for an understanding of the present invention. The MPEG-2 standard defines an encoding scheme for compressing digital representations of video. The encoding scheme takes advantage of the fact that video images generally have large amounts of spatial and temporal redundancy. There is spatial redundancy because a given video picture has sections where the entire area has the same appearance; the larger the areas and the more of them there are, the greater amount of spatial redundancy in the image. There is temporal redundancy because there is often not much change between a given video image and the ones that precede and follow it in a sequence. The less the amount of change between two video images, the greater the amount of temporal redundancy. The more spatial redundancy there is in an image and the more temporal redundancy there is in the sequence of images to which the image belongs, the fewer the bits of information that will be needed to represent the image.
Maximum advantage for the transmission of images encoded using the MPEG-2 standard is obtained if the images can be transmitted at variable bit rates. The bit rates can vary because the rate at which a receiving device receives images is constant, while the images have a varying number of bits. A large image therefore requires a higher bit rate than a small image, and a sequence of MPEG images transmitted at variable bit rates is a variable-rate bit stream with time constraints. For example, a sequence of images that shows a news anchorperson in front of a solid color background will have much more spatial and temporal redundancy than a sequence of images for a commercial or MTV song presentation, and the bit rate for the images showing the news anchor will be far lower than the bit rate for the images of the MTV song presentation.
The MPEG-2 compression scheme presents a sequence of video images as a sequence of compressed pictures, each of which must be decoded at a specific time. There are three ways in which pictures may be compressed. One way is intra-coding, in which the compression is done without reference to any other picture. This encoding technique reduces spatial redundancy but not time redundancy, and the pictures resulting from it are generally larger than those in which the encoding reduces both spatial redundancy and temporal redundancy. Pictures encoded in this way are called I-pictures. A certain number of I-pictures are required in a sequence, first, because the initial picture of a sequence is necessarily an I-picture, and second, because I-pictures permit recovery from transmission errors.
Time redundancy is reduced by encoding pictures as a set of changes from earlier or later pictures or both. In MPEG-2, this is done using motion compensated forward and backward predictions. When a picture uses only forward motion compensated prediction, it is called a Predictive-coded picture, or P picture. When a picture uses both forward and backward motion compensated predictions, it is called a bi-directional predictive-coded picture, or a B picture for short. P pictures generally have fewer bits than I-pictures and B pictures have the smallest number of bits. The number of bits required to encode a given sequence of pictures in MPEG-2 format is thus dependent on the distribution of picture coding types mentioned above, as well as the picture content itself. As will be apparent from the foregoing discussion, the sequence of pictures required to encode the images of the news anchorperson will have fewer and smaller I-pictures and smaller B and P pictures than the sequence required for the MTV song presentation, and consequently, the MPEG-2 representation of the images of the news anchorperson will be much smaller than the MPEG-2 representation of the images of the MTV sequence.
The MPEG-2 pictures are being received by a low-cost consumer electronics device such as a digital television set or a set-top box provided by a cable television ("CATV") service provider. The low cost of the device strictly limits the amount of memory available to store the MPEG-2 pictures. Moreover, the pictures are being used to produce moving images. The MPEG-2 pictures must consequently arrive in the receiver in the right order and with time intervals between them such that the next MPEG-2 picture is available when needed and there is room in the memory for the picture which is currently being sent. In the art, a memory which has run out of data is said to have underflowed, while a memory which has received more data than it can hold is said to have overflowed In the case of underflow, the motion in the TV picture must stop until the next MPEG-2 picture arrives, and in the case of overflow, the data which did not fit into memory is simply lost.
FIG. 1 is a representation of a system 10 including digital picture source 12 and a is television 14 that are connected by a channel 16 that is carrying a MPEG-2 bit stream representation of a sequence of TV images. The digital picture source 12 generates uncompressed digital representations ("UDR") of images 18, which go to variable bit rate ("VBR") encoder 20. Encoder 20 encodes the uncompressed digital representations to produce a variable rate bit stream ("VRBS") 22. Variable rate bit stream 22 is a sequence of compressed digital pictures 24(a . . . n) of variable length. As indicated above, when the encoding is done according to the MPEG-2 standard, the length of a picture depends on the complexity of the image it represents and whether it is an I-picture, a P picture, or a B picture. Additionally, the length of the picture depends on the encoding rate of VBR encoder 20. That rate can be varied. In general, the more bits used to encode a picture, the better the picture quality.
The variable rate bit stream 22 is transferred via channel 16 to VBR decoder 26, which decodes the compressed digital pictures 24(a . . . n) to produce uncompressed digital pictures 28. These in turn are provided to television 14. If television 14 is a digital television, they will be provided directly; otherwise, there will be another element which converts uncompressed digital pictures ("UDP") 28 into standard analog television signals and then provides those signals to television 14. There may of course be any number of VBR decoders 26 receiving the output of a single encoder 20.
In FIG. 1, channel 16 transfers bit stream 22 as a sequence of packets 30. The compressed digital pictures 24 thus appear in FIG. 1 as varying-length sequences of packets 30. Thus, picture 24(a) may have "n" packets while picture 24(n) has "k" packets. Included in each picture 24 is timing information 32. Timing information contains two kinds of information: clock information and time stamps. Clock information is used to synchronize decoder 26 with encoder 20. The MPEG-2 specification refers to this clock information as the Program Clock Reference ("PCR"). The time stamps include the Decoding Time Stamp ("DTS") which specifies when a picture is to be decoded and the Presentation Time Stamp ("PTS") which specifies when it is actually to be displayed. The times specified in the time stamps are specified in terms of the clock information. As indicated above, VBR decoder 26 contains a relatively small amount of memory for storing pictures 24 until they are decoded and provided to TV 14. This memory is shown at 34 in FIG. I and will be referred to hereinafter as the decoder's bit buffer. Bit buffer 34 must be at least large enough to hold the largest possible MPEG-2 picture. Further, channel 16 must provide the pictures 24 to bit buffer 34 in such fashion that decoder 26 can make them available at the proper times to TV 14 and that bit buffer 34 never overflows or underflows. Bit buffer 34 underflows if not all of the bits in a picture 24 have arrived in bit buffer by the time specified in the picture's time stamp for decoder to begin decoding the picture.
Providing pictures 24 to VBR decoder 26 in the proper order and at the proper times is made more complicated by the fact that a number of channels 16 may share a single very high bandwidth data link. For example, a CATV provider may use a satellite link to provide a large number of TV programs from a central location to a number of CATV network head ends, from which they are transmitted via coaxial or fiber optic cable to individual subscribers or may even use the satellite link to provide the TV programs directly to the subscribers. When a number of channels share a medium such as a satellite link, the medium is said to be multiplexed among the channels.
FIG. 2 shows such a multiplexed medium. A number of channels 16(0) through 16(n) which are carrying packets containing bits from variable rate bit streams 22 are received in multiplexer 40, which processes the packets as required to multiplex them onto high bandwidth ("HBW") medium 42. The packets then go via medium 42 to demultiplexer 44, which separates the packets into the packet streams for the individual channels 16 (0 . . . n). A simple way of sharing a high bandwidth medium among a number of channels that are carrying digital data is to repeatedly give each individual channel 16 access to the high bandwidth medium for a short period of time, referred to hereinafter as a slot.
One way of doing this is shown at 50 in FIG. 2. The short period of time appears at 50 as a slot 52; during a slot such as slot 52(0), a fixed number of packets 30 (0 . . . n) belonging to a channel 16 may be output to medium 42. Each channel 16 in turn has a slot 52, and all of the slots taken together make up a time slice 54. When medium 42 is carrying channels like channel 16 that have varying bit rates and time constraints, slot 52 for each of the channels 16 must output enough packets to provide bits at the rate necessary to send the largest pictures to channel 16 within channel 16's time, overflow, and underflow constraints. Of course, most of the time, a channel's slot 52 will be outputting fewer packets than the maximum to medium 42, and sometimes may not be carrying any packets at all. Since each slot 52 represents a fixed portion of medium 42's total bandwidth, any time a slot 52 is not full, a part of medium 42's bandwidth is being wasted.
In order to avoid wasting the medium bandwidth, a technique is used which ensures that each time slice is generally almost fill of packets. This technique is termed statistical multiplexing It takes advantage of the fact that at a given moment of time, each of the channels in a set of channels will be carrying bits at a different bit rate, and the medium bandwidth need only be large enough at that moment of time to transmit what the channels are presently carrying, not large enough to transmit what all of the channels could carry if they were transmitting at the maximum rate. The output of the channels is analyzed statistically to determine what the actual maximum rate of output for the entire set of channels will be and the medium bandwidth is sized to satisfy that actual peak rate. Typically, the bandwidth that is determined in this fashion will be far less than is required for multiplexing in the manner shown at 55 in FIG 2. As a result, more channels can be sent in a given amount of bandwidth. At the level of slots, what statistical multiplexing requires is a mechanism which in effect permits a channel to have a slot in time slice 54 which varies in length to suit the actual needs of channel 16 during that time slice 54. Such a time slice 54 with varying-length slots 56 is shown at 55.
Methods of statistically multiplexing bit streams are disclosed in, for example, U.S. Pat. No. 5,506,844, entitled, Method for Configuring a Statistical Multiplexer to Dynamically Allocate Communication Channel Bandwidth, to Rao, issued Apr. 9, 1996; U.S. patent application Ser. No. 08/823,007 entitled Using a Receiver Model to Multiplex Variable Rate Bit Streams Having Timing Constraints, filed Mar. 21, 1997, the disclosures of each of which are incorporated herein by reference.
While the methods of statistically multiplexing bits streams disclosed in the referenced patents and applications all perform in an adequate manner, there are certain limitations that have come to light. For example, while the Rao patent does disclose a way to maximize the degree to which the Medium's bandwidth is used, it has a number of shortcomings, perhaps the most important of which relates to the fact that it adjusts the multiplexing by changing picture quality. A second shortcoming relates to the fact that it teaches encoders that encode digital images as piece-wise constant bit streams. These bit streams have a lower degree of compression that variable-rate bit streams.
The limitations inherent in the '007 application relate to the fact that while the multiplexer output bandwidth is a fixed constant, the bit rates required of all the channel bit streams changes each time slice to satisfy various requirements of the bit stream, decoder and multiplexer. Each time slice, each of the channels is allocated a portion of the total output of the multiplexer bandwidth. Accordingly, the bit rate allocation is essentially static, and cannot prevent the condition where the sum of the bit rates required by all the channel bit streams for a time slice is greater than the output bandwidth of the multiplexer, a "bandwidth overflow" condition. Likewise, in the prior art the problems associated with bandwidth overflow are dealt with by replacing non-anchor pictures in the MPEG-2 bit stream (e.g., a B picture in an I-B-P sequence, or any I-picture in an all I-picture sequence) with smaller "glue" pictures. While this is an important innovation, it does not alone guarantee the total bandwidth requirements of all channels during a particular time slice will be less than the available output bandwidth of the multiplexer (i.e., does not guarantee prevention of a bandwidth overflow condition). Nor does it provide any means of detecting when overflow is imminent, and which pictures in which channels will be effected.
Accordingly, there exists a need for an improved method of handling potential bandwidth overflow situations. Such an improved method should not only improve allocation of bandwidth, but should also better anticipate imminent bandwidth overflow, and the channels likely effected. All this should also be accomplished without compromising overall effectiveness of the multiplexer.